home *** CD-ROM | disk | FTP | other *** search
/ Deutsche Edition 1 / Deutsche Edition 1.iso / amok / 021-030 / amok22 / bigsets / bigsets.mod < prev    next >
Text File  |  1993-11-04  |  4KB  |  148 lines
  1. (**********************************************************************
  2.  
  3.   :Program.     BigSets.def
  4.   :Contents.    Generic data type: SETs with up to 65335 elements (bits)
  5.   :Author.      Nicolas Benezan [bne]
  6.   :Address.     Postwiesenstr. 2, 7000 Stuttgart 60, Germany
  7.   :Phone.       (0)711 / 33 36 79
  8.   :Copyright.   Public Domain
  9.   :Language.    Modula-2
  10.   :Translator.  M2Amiga AMSoft V3.2d
  11.   :History.     V1.0 [bne] 30.Jan.1989 (PC version)
  12.   :History.     V1.1 [bne] 02.Jul.1989 (Amiga version)
  13.  
  14. **********************************************************************)
  15.  
  16. IMPLEMENTATION MODULE BigSets;
  17.  
  18. FROM Arts       IMPORT Assert;
  19. FROM TaskMemory IMPORT Allocate, Deallocate;
  20. FROM SYSTEM     IMPORT ADDRESS, ADR, BITSET, CAST;
  21.  
  22. TYPE
  23.   BigSet=POINTER TO BigSetBody;
  24.   BigSetBody=(*RECORD
  25.     NumElements:*)CARDINAL;(*
  26.     BitArray:ARRAY [0..NumElements DIV 16] OF BITSET;
  27.   END;*)
  28.   BitSetPtr=POINTER TO BITSET;
  29.  
  30. CONST
  31.   RangeError="BigSets: Range violation";
  32.  
  33. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  34. (* Word aligned size of BigSetBody in bytes                             *)
  35. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  36. PROCEDURE BodySize(NumBits:CARDINAL):CARDINAL;
  37.   BEGIN
  38.     RETURN (NumBits DIV 16)*2+SIZE(BigSetBody);
  39.   END BodySize;
  40.  
  41. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  42. (* Creation                                                             *)
  43. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  44. PROCEDURE CreateBigSet(VAR Set: BigSet;
  45.                            NumElements: CARDINAL): BOOLEAN;
  46.   BEGIN
  47.     BigSetsAllocProc(Set, BodySize(NumElements)+SIZE(BITSET));
  48.     IF Set#NIL THEN
  49.       Set^:=NumElements;
  50.       RETURN TRUE;
  51.     END;
  52.     RETURN FALSE;
  53.   END CreateBigSet;
  54.  
  55. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  56. (* Deletion                                                             *)
  57. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  58. PROCEDURE DiscardBigSet(VAR Set: BigSet);
  59.   BEGIN
  60.     IF Set#NIL THEN
  61.       BigSetsDeallocProc(Set);
  62.       Set:=NIL;
  63.     END;
  64.   END DiscardBigSet;
  65.  
  66. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  67. (* Compute bit position                                                 *)
  68. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  69. PROCEDURE Access(    Set: BigSet;
  70.                  VAR Bit: CARDINAL;
  71.                  VAR SetPtr: BitSetPtr);
  72.   BEGIN
  73.     Assert(Bit<Set^, ADR(RangeError));
  74.     SetPtr:=ADDRESS(LONGINT(Set)+LONGINT(BodySize(Bit)));
  75.     Bit:=Bit MOD 16;
  76.   END Access;
  77.  
  78. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  79. (* Include / Exclude                                                    *)
  80. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  81. PROCEDURE Include(Set: BigSet;
  82.                   Bit: CARDINAL);
  83.   VAR
  84.     SetPtr: BitSetPtr;
  85.   BEGIN
  86.     Access(Set, Bit, SetPtr);
  87.     INCL(SetPtr^, Bit);
  88.   END Include;
  89.  
  90. PROCEDURE Exclude(Set: BigSet;
  91.                   Bit: CARDINAL);
  92.   VAR
  93.     SetPtr: BitSetPtr;
  94.   BEGIN
  95.     Access(Set, Bit, SetPtr);
  96.     EXCL(SetPtr^, Bit);
  97.   END Exclude;
  98.  
  99. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  100. (* Test bit                                                             *)
  101. (*­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­*)
  102. PROCEDURE BitInSet(Set: BigSet;
  103.                    Bit: CARDINAL): BOOLEAN;
  104.   VAR
  105.     SetPtr: BitSetPtr;
  106.   BEGIN
  107.     Access(Set, Bit, SetPtr);
  108.     RETURN Bit IN SetPtr^
  109.   END BitInSet;
  110.  
  111. PROCEDURE FindNextClear(    Set: BigSet;
  112.                         VAR Bit: CARDINAL): BOOLEAN;
  113.   VAR
  114.     SetPtr: BitSetPtr;
  115.     Pos, Test: CARDINAL;
  116.   BEGIN
  117.     Pos:=Bit;
  118.     Access(Set, Bit, SetPtr);
  119.     DEC(Pos, Bit);
  120.     FOR Pos:=Pos TO Set^-1 BY 16 DO
  121.       IF CAST(CARDINAL, SetPtr^)#0FFFFH THEN
  122.         FOR Test:=Bit TO 15 DO
  123.           IF NOT (Test IN SetPtr^) THEN
  124.             Bit:=Pos+Test;
  125.             RETURN Bit<Set^
  126.           END;
  127.         END;
  128.       END;
  129.       Bit:=0;
  130.       INC(SetPtr, SIZE(BITSET));
  131.     END;
  132.  
  133. (*  BEGIN
  134.     WHILE BitInSet(Set, Bit) DO
  135.       INC(Bit);
  136.       IF Bit>=Set^ THEN
  137.         RETURN FALSE
  138.       END;
  139.     END;
  140.     RETURN TRUE; *)
  141.   END FindNextClear;
  142.  
  143. BEGIN
  144.   BigSetsAllocProc:=Allocate;
  145.   BigSetsDeallocProc:=Deallocate;
  146. END BigSets.
  147.  
  148.